package com.lijing.backTracing;

import java.nio.file.Path;
import java.util.*;

/**
 * @Description backTracing leetCode 77
 * @title: BackTracing77
 * @Author LiJing
 * @Date: 2021/4/21:51 下午
 * @Version 1.0
 */
public class BackTracing77 {
    static Stack<Object> path;
    static List<Stack<Object>> result;

    public static void main(String[] args) {
        Integer[] arr = {1,3,4,5,7,9,8};
        BackTracing77 backTracing77 = new BackTracing77();
        backTracing(arr,5,0);
        showResult();


    }

    public BackTracing77() {
        path = new Stack<Object>();
        result = new ArrayList<Stack<Object>>();
    }

    public static void backTracing(int n, int k, int startIndex){
        /*
         * @Date: 2021/4/2 2:02 下午
         * Step 1: 判断终止条件，存放结果，并返回
         */
        if (path.size() == k){
            Stack<Object> path1 = (Stack<Object>)path.clone();
            result.add(path1);
            return;
        }

        /*
         * @Date: 2021/4/2 2:05 下午
         * Step 2: 横向遍历集合，先处理节点，然后纵向递归，在进行回溯操作
         */
        for (int i = startIndex; i <= n-(k-path.size())+1; i++) {
            //先把第i个元素入栈
            path.push(i);
            //递归
            backTracing(n,k,i+1);
            path.pop();
        }
    }
    public static void showResult(){
        for (Stack<Object> stackRes : result){
            System.out.println(stackRes);
        }
    }

    public static void backTracing(Object[] objects, int k, int startIndex){
        if (path.size() == k){
            Stack stack = (Stack) path.clone();
            result.add(stack);
            return;
        }
        for (int i = startIndex; i < objects.length-(k-path.size())+1; i++) {
            path.push(objects[i]);
            backTracing(objects,k,i+1);
            path.pop();
        }
    }

}
